class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        def swap(string, i, j):
            temp = string[j]
            trailer = string[j + 1:]
            string = string[:j] + string[i] + trailer
            string = string[:i] + temp + string[i + 1:]
            return string

        queue = []
        queue.append(A)
        layer = 0
        visited = set()
        while queue:
            for _ in range(len(queue)):
                cur = queue.pop(0)
                visited.add(cur)
                if cur == B:
                    return layer
                i = 0
                while i < len(cur) and cur[i] == B[i]:
                    i += 1
                for j in range(i + 1, len(cur)):
                    if cur[j] == B[j] or cur[j] != B[i]:
                        continue
                    newString = swap(cur, i, j)
                    if newString not in visited:
                        queue.append(newString)
            layer += 1

        return -1
